PPO: Proximal Policy Optimization
The idea of PPO can be summarized as: allow the policy to update, but constrain the policy from changing too much, in order to stablize training. Compared to prior work TRPO that uses second-order methods which requires massive computation, PPO uses first-order methods to achieve the same goal.
Table of Contents
1. Motivation
In traditional RL, we have state \(s_{t}\), action \(a_{t}\), reward \(r_{t}\) and policy \(\pi_{\theta}(a|s)\). We want to maximize the expected cumulative reward:
\[ J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}}\left[ \sum_{t=0}^{T} \gamma^{t}r_{t} \right] \]
where \(\tau = (s_{0},a_{0},r_{0}, s_{1}, a_{1}, r_{1}, \dots)\) denotes the trajectory.
If we parameterize the policy \(\pi_{\theta}(a|s)\), the Policy Gradient Theorem tells us that
\[ \nabla_{\theta} J(\theta) = \mathbb{E}[\nabla_{\theta} \log \pi_{\theta}(a_{t}|s_{t}) A^{\pi}(s_{t}, a_{t})] \]
where \(A^{\pi}(s_{t}, a_{t}) = Q^{\pi}(s_{t}, a_{t}) - V^{\pi}(s)\) is the advantage, the superscript is to tell that this advantage/value/Q-state is computed under policy \(\pi\). Intuitively, if \(A^{\pi}\gt 0\), then this action does better, we want to increase the probability that we sample \(a_{t}\), i.e., increase \(\pi_{\theta}(a_{t}|s_{t})\); otherwise, if \(A^{\pi}\lt 0\), this tells us that this action is worse then others, therefore decreasing its probability, i.e., lowering \(\pi_{\theta}(a_{t}|s_{t})\).
This comes the challenge: a single gradient update could change the behaviour of a policy too much. The point here is that, if the policy is “bad”, trajectories collected using “bad” policy may not be able to pull the policy back to the correct direction. And if the policy changes too much, it’s very likely to make the policy “worse”. Therefore, typical problems in RL training includes learning collapse, reward collapse, gradient instability, and catastrophic policy update.
2. Proximal Policy Optimization
Let’s apply the importance sampling trick1. Define importance weight
\[ w_{t}(\theta) = \frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{\text{old}}}(a_{t}|s_{t})} \]
Intuitively, the importance weight could measure the change of probability between new and old policies.
Then, we introduce the most important part in PPO, the PPO objective function.
\begin{equation} L^{\text{CLIP}}(\theta) = \mathbb{E}_{t}\left[ \min \left( w_{t}(\theta)\hat{A}_{t}, \mathrm{clip}(w_{t}(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_{t} \right) \right] \end{equation}The key part is the clipping \([1-\epsilon, 1+\epsilon])\). Given \(\hat{A}_{t}\) could be both positive and negative, this clipping constrains \(\hat{A}_{t}\) at a region.
2.1. Generalized Advantage Estimation
Monte-Carlo style estimation of advantage is
\[ \hat{A}^{MC}_{t} = G_{t} - V_{\omega}(s_{t}) = \left( \sum_{k=0}^{T-t} \gamma^{k}r_{t+k} \right) - V_{\omega}(s_{t}) \]
And single-step temporal difference estimation (a.k.a. temporal difference error) of advantage is
\[ \hat{A}^{TD}_{t} = r_{t} + \gamma V_{\omega}(s_{t+1}) - V_{\omega}(s_{t}) \]
While Monte-Carlo style estimation is unbiased, it suffers from high variance; in contrast, temporal difference estimation has low variance, but is biased (subject to how well the value model \(V_{\omega}\) is).
Generalized Advantage Estimation (GAE) is a mixture of MC and TD approach, through an adjustable formula:
\begin{equation} \hat{A}_{t}^{GAE(\gamma,\lambda)} = \sum_{l=0}^{\infin} (\gamma\lambda)^{l} \delta_{t+l} \end{equation}where \(\delta_{t+l} = r_{t+l} + \gamma V_{\omega}(s_{t+l+1}) - V_{\omega}(s_{t+l})\) is the TD error of step \(t+l\). \(\lambda \in [0,1]\) is a new hyperparameter.
To some extent, this formula takes the weighted average of future temporal difference errors of all steps, where the weights are decreasing by \((\gamma\lambda)^{l}\).
- When \(\lambda=0\), then \(\hat{A}_{t} = \delta_{t}\), which is exactly TD estimation
- When \(\lambda=1\), then this series can be cancelled out and becomes \(\hat{A}_{t} = G_{t} - V_{\omega}(s_{t})\), which is exactly MC estimation.
In practice, we usually take \(\lambda \in [0.9, 0.97]\). And also, we usually compute reversely to speed up computation:
\[ \hat{A}_{t} = \delta_{t} + \gamma \lambda \hat{A}_{t+1} \]
Footnotes:
Importance sampling answers the question that how to estimate the expectation under distribution \(p\) while data are sampled from distribution \(q\).